package Leetcode.搜索与回溯;

import java.util.*;

/**
 * @Author kirito
 * @Date 2023/11/16 10:39
 * @PackageName:Leetcode.搜索与回溯
 * @ClassName: 全排列2
 * @Description:
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 *  [1,2,1],
 *  [2,1,1]]
 * 示例 2：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * @Version 1.0
 */
public class 全排列2 {
    boolean[] vis; // 用于标记元素是否已经被访问过

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>(); // 存储最终的排列结果
        List<Integer> perm = new ArrayList<Integer>(); // 存储当前排列的元素列表
        vis = new boolean[nums.length]; // 初始化标记数组，默认所有元素都未被访问过
        Arrays.sort(nums); // 对输入数组进行排序，确保重复元素相邻

        // 调用回溯函数，生成排列结果
        backtrack(nums, ans, 0, perm);

        return ans; // 返回最终的排列结果
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        // 当所有元素都被访问过，即完成了一种排列，将当前排列添加到结果列表中
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }

        for (int i = 0; i < nums.length; ++i) {
            // 如果元素已经被访问过，或者当前元素和前一个元素相同且前一个元素未被访问过，则跳过当前元素
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }

            perm.add(nums[i]); // 将当前元素添加到排列中
            vis[i] = true; // 标记当前元素为已访问
            backtrack(nums, ans, idx + 1, perm); // 继续递归生成下一个位置的元素
            vis[i] = false; // 回溯，撤销当前元素的访问状态
            perm.remove(idx); // 移除当前位置的元素，以便尝试其他元素
        }
    }


}
